#include "global.h"
#include "hMap.h"

using namespace std;


vector<double> k = { 0.15, 0.1, 0.05, 0.1, 0.2 };
vector<double> d = { 0.05, 0.1, 0.05, 0.05, 0.05, 0.1 };

struct Solution
{
	double _e = 0;
	size_t _r = 0;

	void show() const
	{

	}
};

struct Method
{
	map<size_t, map<size_t, Solution>> _solutions;

	Solution& bottomUp()
	{
		map<size_t, map<size_t, double>> w;
		for (size_t i = 0; i < d.size(); ++i)
		{
			_solutions[i + 1][i] = { d[i], 2 * i };
			w[i + 1][i] = d[i];
		}

		for (size_t i = 0; i < k.size(); ++i)
		{
			size_t dif = k.size() - i;
			for (size_t j = 0; j < dif; ++j)
			{
				double& tmpW = w[j + 1][j + i + 1];
				tmpW = w[j + 1][j + i] + k[j + i] + d[j + i + 1];

				Solution& s = _solutions[j + 1][j + i + 1];
				s._e = std::numeric_limits<double>::max();
				for (size_t r = 0; r <= i; ++r)
				{
					double e = _solutions[j + 1][j + r]._e + _solutions[j + r + 2][j + i + 1]._e + tmpW;
					if (s._e > e)
					{
						s._e = e;
						s._r = 2 * (r + j) + 1;
					}
				}
			}
		}

		return _solutions[1][k.size()];
	}

	void fillMap(hMap<size_t, string>& m) const
	{
		fillMapCallback(m, 1, k.size());
	}

	void fillMapCallback(hMap<size_t, string>& m, size_t i, size_t j) const
	{
		auto itMap = _solutions.find(i);
		if (itMap == _solutions.end())
		{
			cout << "Err itMap:" << i << "," << j << endl;
			return;
		}

		auto it = itMap->second.find(j);
		if (it == itMap->second.end())
		{
			cout << "Err it:" << i << "," << j << endl;
			return;
		}

		const Solution& s = it->second;
		ostringstream os;
		size_t type = s._r % 2;
		size_t id = s._r / 2 + 1;
		if (type)
			os << 'k' << id;
		else
			os << 'd' << id - 1;

		m.emplace(s._r, os.str());
		if (!type)
			return;

		fillMapCallback(m, i, id - 1);
		fillMapCallback(m, id + 1, j);
	}
};

int main()
{
	Method meth;
	auto& s = meth.bottomUp();
	cout << s._e << " " << s._r << endl;

	hMap<size_t, string> m;
	meth.fillMap(m);
	m.fillDebug(cout) << endl;

	return 0;
}
